package algorithm.sort.nlogn;

import algorithm.sort.n2.HelperTest;
import algorithm.sort.n2.SelectionSort;

/**
 * @author: Oliver
 * @time: 2020/6/1/10:58
 */
public class QuickSort3Ways {
    public static void sort(Comparable[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    // 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void quickSort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        // 进行选出中间分割点，也就是怎么分
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        int randomV = (int) (Math.random() * (r - l + 1) + l);
        SelectionSort.swap(arr, l, randomV);
        Comparable v = arr[l];
        // 进行partition操作 解决重复元素排序时遇到的切割不均匀的情况
        //定义lt   i   gt 使得arr[l+1,lt]<v  [lt+1,i-1)=v  [gt,r]>v  lt指向当前<v的最后一个元素，gt指向当前1大于v的第一个元素。
        // i指向当前正要比较的元素
        int lt = l; //arr[l+1...lt] < v  因为此时集合为范围为空
        int gt = r + 1;//arr[gt...r] > v  此时集合为空满足定义
        int i = l + 1; //arr[lt+1...i) == v
        while (i < gt) {//说明已经操作结束 i大于等于gt说明操作结束
            //如果当前元素<v 交换 lt i ,维护lt i
            if (arr[i].compareTo(v) < 0) {
                SelectionSort.swap(arr, lt + 1, i);
                lt++;
                i++;
            } else if (arr[i].compareTo(v) > 0) {
                //如果当前元素比v大，则将gt--位置对应元素进行与i交换，此时i又为新的元素，不用维护i
                SelectionSort.swap(arr, i, gt - 1);
                gt--;
            } else {
                //说明和v相等，也就是说此时不需要改变 只需要使i指向下一个需要判断的元素即可
                i++;
            }
        }
        //和最后一个比v小的元素进行交换 ,返回的是一个数组，所以在下面进行切分的时候需要借助gt,lt
        SelectionSort.swap(arr, l, lt);
        quickSort(arr, l, lt - 1);//lt-1 是因为在上面将l位置元素与 lt上元素进行交换了，使得arr[lt]==v
        quickSort(arr, gt, r);
    }

    // 测试 QuickSort
    public static void main(String[] args) {

        // Quick Sort也是一个O(nlogn)复杂度的算法
        // 可以在1秒之内轻松处理100万数量级的数据
        Integer[] arr = {12, 23, 34, 45, 56, 1, 2, 1};
        sort(arr);
        HelperTest.printArray(arr);
        return;
    }
}
